package 高效制胜._10;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/17 20:26
 * K 站中转内最便宜的航班
 * 算法：广度优先搜索
 */
public class _787 {
    public static void main(String[] args) {
//        System.out.println(new _787().findCheapestPrice(4,
//                new int[][]{{0,1,1},{0,2,5},{1,2,1},{2,3,1}},
//                0, 3, 1));
        int k = 0;
        while (k-- >= 0) System.out.println(k);
    }

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> paths = new HashMap<>(n);
        for (int[] flight : flights) {
            final List<int[]> list = paths.getOrDefault(flight[0], new ArrayList<>());
            list.add(new int[]{flight[1], flight[2]});
            paths.put(flight[0], list);
        }
        Deque<int[]> queue = new LinkedList<>();
        queue.add(new int[]{src, 0});
        // 不剪枝过不去
        int[] ans = new int[n];
        Arrays.fill(ans, Integer.MAX_VALUE);
        while (k + 1 > 0 && !queue.isEmpty()) {
            final int size = queue.size();
            for (int i = 0; i < size; i++) {
                // poll[1] 表示到这个节点要多少钱
                final int[] poll = queue.poll();
                final List<int[]> list = paths.getOrDefault(poll[0], new ArrayList<>());
                for (int[] path : list) {
                    // path[0] 表示当前节点能到的节点, path[1] 表示当前节点到 path[0] 所需的 money
                    int money = poll[1] + path[1];
                    if (money < ans[path[0]] && money < ans[dst]) {
                        ans[path[0]] = money;
                        if (path[0] != dst) queue.offer(new int[]{path[0], money});
                    }
                }
            }
            --k;
        }
        return ans[dst] == Integer.MAX_VALUE ? -1 : ans[dst];
    }

}
